package B.链表;

import java.util.HashMap;
import java.util.Map;

public class _141_环形链表 {
    /**
     * 自解：利用hash表来判断
     * @param head
     * @return
     */
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null ){
            return false;
        }
        ListNode pre = null;
        ListNode cur = head;

        Map<ListNode,ListNode> map = new HashMap<>();//key存前结点 value存当前结点

        while (!map.containsKey(pre)){
            map.put(pre,cur);
            pre =cur;
            if (null != cur.next){
                cur = cur.next;
            } else {
                return false;
            }
        }
            return true;

    }
    /**
     * Floyd 判圈算法--快慢双指针
     * 定义两个指针，一快一满。慢指针每次只移动一步，而快指针每次移动两步。初始时，慢指针在位置 head，而快指针在位置 head.next。这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表
     *
     * 慢指针在head  快指针在。next 快指针每次移动两个 慢指针移动一个 如果有环 快指针与慢指针就会重复
     */
    public boolean hasCycle1(ListNode head){
        if (head == null || head.next == null){
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;

        while (slow != fast){
            if (fast ==null || fast.next==null){
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;

        }
        return true;




    }
}
